﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConfExpert.Utility
{
    public class Solver
    {

        private List<List<int>> mResults;
        public long IterationCount = 0;
        public decimal delta = 1;
        public List<List<int>> Solve(int goal, Dictionary<int,decimal> elements)
        {
            mResults = new List<List<int>>();
            RecursiveSolve(goal,
                0.0m,
                new Dictionary<int,decimal>(),
                new Dictionary<int,decimal>(elements),
                0);
            return mResults;
        }

        //timer ile 15 sn.'de kes ve deltayı artırmayı öner!

        bool found = false;
        private void RecursiveSolve(int goal, decimal currentSum, Dictionary<int, decimal> included, Dictionary<int,decimal> notIncluded, int startIndex)
        {
            if (IterationCount > 3e6)
                return;

            var mover = notIncluded.GetEnumerator();
            
            mover.MoveNext();

            for (int index = startIndex; index < notIncluded.Count; index++)
            {
                IterationCount++;
                decimal nextValue = mover.Current.Value;
                int nextKey = mover.Current.Key;
                   

                if (Math.Abs(goal - (currentSum + nextValue)) < delta && !found)
                {
                    List<int> newResult = new List<int>();
                    var includedMover = included.GetEnumerator();
                    while (includedMover.MoveNext())
                    {
                        newResult.Add(includedMover.Current.Key);
                    }
                    newResult.Add(mover.Current.Key);   
                    
                    mResults.Add(newResult);
                    found = true;
                    return;
                }
                else if (goal - (currentSum + nextValue) > 0)
                {
                    Dictionary<int, decimal> nextIncluded = new Dictionary<int, decimal>(included);
                    
                    nextIncluded.Add(nextKey,nextValue);

                    Dictionary<int, decimal> nextNotIncluded = new Dictionary<int, decimal>(notIncluded);
                    nextNotIncluded.Remove(nextKey);

                    if (!found)
                        RecursiveSolve(goal, currentSum + nextValue, nextIncluded, nextNotIncluded, startIndex++);

                }
                mover.MoveNext(); 
            }
        }


    }
}



namespace ConfExpert.Utility
{
    public class Solver2
    {

        private List<List<decimal>> mResults;
        public long IterationCount = 0;
        public decimal delta = 1;
        public List<List<decimal>> Solve(int goal, decimal[] elements)
        {
            mResults = new List<List<decimal>>();
            RecursiveSolve(goal,
                0.0m,
                new List<decimal>(),
                new List<decimal>(elements),
                0);
            return mResults;
        }

        //timer ile 15 sn.'de kes ve deltayı artırmayı öner!

        bool found = false;
        private void RecursiveSolve(int goal, decimal currentSum, List<decimal> included, List<decimal> notIncluded, int startIndex)
        {
            if (IterationCount > 3e6)
                return;

            for (int index = startIndex; index < notIncluded.Count; index++)
            {
                IterationCount++;
                decimal nextValue = notIncluded[index];

                if (Math.Abs(goal - (currentSum + nextValue)) < delta && !found)
                {
                    List<decimal> newResult = new List<decimal>(included);
                    newResult.Add(nextValue);   //burada RollId yi de kaydet!
                    mResults.Add(newResult);
                    found = true;
                    return;
                }
                else if (goal - (currentSum + nextValue) > 0)
                {
                    List<decimal> nextIncluded = new List<decimal>(included);
                    nextIncluded.Add(nextValue);
                    List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
                    nextNotIncluded.Remove(nextValue);

                    if (!found)
                        RecursiveSolve(goal, currentSum + nextValue, nextIncluded, nextNotIncluded, startIndex++);

                }
            }
        }


    }
}